package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，
 * 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
 * <p>
 * i - K <= r <= i + K, j - K <= c <= j + K
 * (r, c) 在矩阵内。
 * <p>
 * 示例 1：
 * <p>
 * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
 * 输出：[[12,21,16],[27,45,33],[24,39,28]]
 *
 * @author caijinnan
 * @date 2020/3/18 14:40
 */
public class 矩阵区域和 {

    @Test
    public void run() {
        int[][] mat = {{67, 64, 78}, {99, 98, 38}, {82, 46, 46}, {6, 52, 55}, {55, 99, 45}};
        int K = 3;
        for (int[] temp : matrixBlockSum(mat, K)) {
            System.out.println(Arrays.toString(temp));
        }
    }
    //右边一个方块的总和等于左边减去最左边一列的和加上最右边新增一列的和,同理下边一个方块与上一行一个方块的关系;
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int yLength = mat.length;
        int xLength = mat[0].length;

        int[][] resultArr = new int[yLength][xLength];
        int initSum = 0;
        for (int x = 0; x <= k && x < xLength; x++) {
            for (int y = 0; y <= k && y < yLength; y++) {
                initSum += mat[y][x];
            }
        }
        resultArr[0][0] = initSum;
        for (int y = 0; y < yLength; y++) {
            for (int x = 0; x < xLength; x++) {
                if (x == 0 && y == 0) {
                    continue;
                }
                int sumTemp = 0;
                if (x == 0) {
                    for (int xTemp = Math.max(x - k, 0); xTemp <= Math.min(x + k, xLength - 1); xTemp++) {
                        int subYTemp = y - k - 1;
                        int addYTemp = y + k;
                        sumTemp += (y + k < yLength ? mat[addYTemp][xTemp] : 0) - (y - k - 1 < 0 ? 0 : mat[subYTemp][xTemp]);
                    }
                    resultArr[y][x] = resultArr[y - 1][x] + sumTemp;
                } else {
                    for (int yTemp = Math.max(y - k, 0); yTemp <= Math.min(y + k, yLength - 1); yTemp++) {
                        int subXTemp = Math.max(x - k - 1, 0);
                        int addXTemp = x + k;
                        sumTemp += (x + k < xLength ? mat[yTemp][addXTemp] : 0) - (x - k - 1 < 0 ? 0 : mat[yTemp][subXTemp]);
                    }
                    resultArr[y][x] = resultArr[y][x - 1] + sumTemp;
                }
            }
        }
        return resultArr;
    }
}
